package 排序; // 定义包名为“排序”
import java.util.*; // 导入java工具包

public class topKFrequent { // 定义类，用于查找出现频率最高的k个元素
    public int[] topKFreq(int[] nums, int k){ // 方法用于返回出现频率最高的k个元素
        HashMap<Integer, Integer> map = new HashMap<>(); // 创建一个哈希表用于存储每个元素的出现次数
        for(int num : nums){ // 遍历数组，统计每个元素的出现次数
            map.put(num, map.getOrDefault(num, 0) + 1); // 更新哈希表中的计数
        }
        int[][] arr = new int[nums.length][2]; // 创建一个二维数组用于存储元素及其出现次数
        int idx = 0; // 初始化索引
        for(int key : map.keySet()){ // 遍历哈希表的键
            arr[idx] = new int[]{key, map.get(key)}; // 将元素及其出现次数存入二维数组
            idx++; // 索引递增
        }
        // Arrays.sort(arr, (o1, o2) -> o1[1] - o2[1]); // 使用Java内置排序
        quickSort(arr, 0, arr.length - 1); // 对二维数组进行快速排序
        int[] res = new int[k]; // 创建一个数组用于存储结果
        for(int i = 0; i < k; i++){ // 遍历k次
            res[i] = arr[arr.length - 1 - i][0]; // 将出现频率最高的k个元素存入结果数组
        }
        return res; // 返回结果数组
    }

    private void quickSort(int[][] arr, int left, int right){ // 快速排序算法
        if(left >= right) return; // 如果左边界大于等于右边界，返回
        int pivot = partition(arr, left, right); // 获取基准元素的位置
        quickSort(arr, left, pivot - 1); // 递归排序左半部分
        quickSort(arr, pivot + 1, right); // 递归排序右半部分
    }

    private int partition(int[][] arr, int left, int right){ // 分区函数，用于快速排序
        int[] val = arr[left]; // 选择第一个元素作为基准
        while(left < right){ // 当左边界小于右边界时继续循环
            while(left < right && arr[right][1] >= val[1]) right--; // 从右向左找小于基准的元素
            arr[left] = arr[right]; // 将小于基准的元素放到左边
            while(left < right && arr[left][1] <= val[1]) left++; // 从左向右找大于基准的元素
            arr[right] = arr[left]; // 将大于基准的元素放到右边
        }
        arr[left] = val; // 将基准元素放到最终位置
        return left; // 返回基准元素的位置
    }

    public static void main(String[] args) { // 主方法，处理输入并输出结果
        Scanner sc = new Scanner(System.in); // 创建扫描器对象
        String[] s = sc.nextLine().split(","); // 读取输入并分割
        int k = sc.nextInt(); // 读取k值
        int[] nums = new int[s.length]; // 创建数组用于存储输入的元素
        for(int i = 0; i < s.length; i++){ // 遍历输入的元素
            nums[i] = Integer.parseInt(s[i]); // 将字符串转换为整数
        }
        topKFrequent tkf = new topKFrequent(); // 创建对象
        System.out.println(Arrays.toString(tkf.topKFreq(nums, k))); // 输出结果
        sc.close(); // 关闭扫描器
    }
}
